# 冒泡
def bubble_sort(arr):
    for i in range(0, len(arr) - 1):
        # 若一次循环完了之后没有进行交换，说明arr本身就有序，后续循坏无序再做。
        swapped = False
        for j in range(0, len(arr) - 1 - i):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        if not swapped:
            break
    return arr


# 选择
def select_sort(arr):
    for i in range(0, len(arr) - 1):
        # 从待排序的数组中选出最小的元素索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # 交换位置
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr


# 插入
def insertion_sort(arr):
    for loop_index in range(1, len(arr)):
        insertion_index = loop_index
        # 前一个大于后一个数字就交换位置
        while insertion_index > 0 and arr[insertion_index - 1] > arr[insertion_index]:
            # 交换位置
            arr[insertion_index - 1], arr[insertion_index] = arr[insertion_index], arr[insertion_index - 1]
            # 继续往前循环
            insertion_index -= 1
    return arr


# 快速
def quick_sort(arr):
    # 递归退出的条件
    length = len(arr)
    if length <= 1:
        return arr
    else:
        # 可以选第一个元素作为基准值，也可以选最后一个
        pivot = arr.pop()
        greater, lesser = [], []
        for element in arr:
            if element > pivot:
                greater.append(element)
            else:
                lesser.append(element)
        return quick_sort(lesser) + [pivot] + quick_sort(greater)


list_1 = [6, 2, 1, 4, 3]
print(select_sort(list_1))
print(bubble_sort(list_1))
print(insertion_sort(list_1))
print(quick_sort(list_1))
